package graph;

import java.util.Arrays;
import java.util.OptionalInt;

public class BellmanFord {


    public static void main(String[] args) {
    }

    /**
     * @param n 一共有多少个飞机站
     * @param flights [[起点站a，终点站b, price]]
     * @param start 起点站
     * @param target 终点站
     * @param k 允许的转机次数
     * @return 最便宜的价格
     */
    public static OptionalInt findCheapestPrice(int n, int[][] flights, int start, int target, int k) {
        int[] cur = new int[n];
        // 起点到所有其它地点距离初始化为最大
        Arrays.fill(cur, Integer.MAX_VALUE);
        cur[start] = 0;
        for (int i = 0; i <= k; i++) {
            int[] next = Arrays.copyOf(cur, n);
            for (int[] edge : flights) {
                if (cur[edge[0]] != Integer.MAX_VALUE) {
                    // 这条边的from点到start点的距离更新过
                    // 起点到to点的距离 = 原来记录的距离，from点到start点的距离 + 当前边的距离。较小的一个
                    next[edge[1]] = Math.min(next[edge[1]], cur[edge[0]] + edge[2]);
                }
            }
            cur = next;
        }

        return cur[target] == Integer.MAX_VALUE ? OptionalInt.empty() : OptionalInt.of(cur[target]);
    }
}
